#include <cstdio>
#include <memory.h>
#include <queue>
#include <iostream>
using namespace std;

struct node {
	int x, w;
	node(int v, int wi) {x = v; w = wi;}
};

int n, m;
int tx[1005];
long long dis[1005];
bool inq[1005], vis[1005];
queue<int> q;
vector<node> G[1005];

bool spfa(int s) {
	memset(dis, 0x7f, sizeof(dis));
	dis[s] = 0;
	q.push(s);
	tx[s] = 1;
	while (q.size()) {
		int x = q.front();
		vis[x] = 1;
		q.pop();
		inq[x] = 0;
		for (unsigned i = 0; i < G[x].size(); ++i) {
			int y = G[x][i].x, z = G[x][i].w;
			if (dis[y] > dis[x] + z) {
				dis[y] = dis[x] + z;
				if (++tx[y] >= n) return 0;
				if (!inq[y]) {
					q.push(y);
					inq[y] = 1;
				}
			}
		}
	}
	return 1;
}

int main() {
	int s;
	cin >> n >> m >> s;
	int u, v, w;
	for (int i = 1; i <= m; ++i) {
		cin >> u >> v >> w;
		G[u].push_back(node(v, w));
	}

	long long inf;
	memset(&inf, 0x7f, sizeof(inf));

	bool flag = 1;
	for (int i = 1; i <= n; ++i) {
		if (!vis[i]) {
			if(!spfa(i)) {
				flag = 0;
				break;
			}
		}
	}
	spfa(s);

	if (flag) {
		for (int i = 1; i <= n; ++i) {
			if (dis[i] < inf) printf("%lld\n", dis[i]);
			else printf("NoPath\n");
		}
	} else {
		printf("-1\n");
	}
	return 0;
}